//
//  CCOther.h
//  leetcode
//
//  Created by hellobike07499 on 2019/9/6.
//  Copyright © 2019 hellobike07499. All rights reserved.
//

#ifndef CCOther_h
#define CCOther_h
#include <iostream>
#include <vector>

using namespace std;

class CCOther{
public:
    void test(){
        test3();
    }
    
    void test0(){
        cout << hammingWeight(1) << endl;
        cout << hammingWeight(9)<< endl;
        
        cout << hammingDistance(1, 4) << endl;
    }
    
    void test1(){
        cout << reverseBits(5) << endl;
    }
    
    void test2(){
        vector<vector<int>> all =  generate(10);
        
        for (int r = 0; r < all.size(); r++) {
            vector<int> row = all[r];
            for (int c = 0; c < row.size(); c++) {
                cout << row[c] <<  ",";
            }
            cout << endl;
        }
    }
    
    void test3(){
        cout << "() :::" << (isValid("()") ? "yes" : "no") << endl;
        cout << "()[]{} :::" << (isValid("()[]{}") ? "yes" : "no") << endl;
        cout << "(] :::" << (isValid("(]") ? "yes" : "no") << endl;
        
        cout << "([)] :::" << (isValid("([)]") ? "yes" : "no") << endl;
        cout << "{[]} :::" << (isValid("{[]}") ? "yes" : "no") << endl;
    }
    
public:
    int hammingWeight(uint32_t n) {
        uint32_t tmp = n;
        if(tmp == 0) return 0;
        
        int count = 0;
        while(tmp > 0){
            if((tmp & 0x01) == 0x01){
                count++;
            }
            tmp = tmp >> 0x01;
        }
        
        return count;
    }
    
    int hammingDistance(int x, int y) {
        int tmp = x xor y;
        return hammingWeight(tmp);
    }
    
    uint32_t reverseBits(uint32_t n) {
        uint32_t tmp = 0;
        int i = 0;
        while(i < 32){
            uint32_t bit = n >> i & 0x01;
            tmp = tmp xor (bit << (32 - i -1));
            
            i++;
        }
        return tmp;
    }
    
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> all;
        if(numRows < 0) return all;
        
        for (int r = 0; r < numRows; r++) {
            vector<int> row;
            for (int c = 0; c < (r + 1); c++) {
                if(c == 0 || c == r){
                    row.push_back(1);
                    continue;
                }
                
                int v = all[r - 1][c - 1] + all[r - 1][c];
                row.push_back(v);
            }
            
            all.push_back(row);
        }
        return all;
    }
    
    bool isValid(string s) {
        if(s.length() == 0) return true;
        
        stack<char> sChar;
        for (int i = 0; i < s.length(); i++) {
            char cur = s[i];
            if(sChar.size() == 0){
                sChar.push(cur);
                continue;
            }
            
            if(cur == ')' && sChar.top() == '('){
                sChar.pop();
            }else if(cur == '}' && sChar.top() == '{'){
                sChar.pop();
            }else if(cur == ']' && sChar.top() == '['){
                sChar.pop();
            }else{
                sChar.push(cur);
            }
            
        }
        
        if(sChar.size() == 0) return true;
        
        return false;
    }
    
    int missingNumber(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        
        vector<bool> all(nums.size() + 1, false);
        for (int i = 0; i < nums.size(); i++) {
            all[nums[i]] = true;
        }
        for (int i = 0; i < all.size(); i++) {
            if(!all[i]){
                return i;
            }
        }
        return 0;
    }
};

#endif /* CCOther_h */
